/**
 * 1641. 统计字典序元音字符串的数目
 * https://leetcode-cn.com/problems/count-sorted-vowel-strings/
 */
public class Solutions_1641 {
    public static void main(String[] args) {
//        int n = 1;
        for (int n = 1; n <= 50; n++) {
            int result = countVowelStrings(n);
            System.out.println(result);
        }
    }

    /**
     * 解题思路：找规律
     * 当 n 增加一个长度时，对于已有的所有组合结果，都有以下变化：
     * 以 a e i o u 开头的，都可以在 开头 再加 1 个 a
     * 以   e i o u 开头的，都可以在 开头 再加 1 个 e
     * 以     i o u 开头的，都可以在 开头 再加 1 个 i
     * ...
     */
    public static int countVowelStrings(int n) {
        int a = 1, e = 1, i = 1, o = 1, u = 1;
        for (int k = 2; k <= n; k++) {
            a = a + e + i + o + u;
            e = e + i + o + u;
            i = i + o + u;
            o = o + u;
        }
        return a + e + i + o + u;
    }
}
